


from Crypto.Util.number import *
from random import *
import libnum
import uuid
import os
import gmpy2

flag = "flag{" + str(uuid.uuid4()) + "}"
flag = libnum.s2n(flag.encode()+os.urandom(30))
print(gmpy2.bit_length(flag))
BITS = 512
p = getPrime(BITS)
q = getPrime(BITS)
n = p*q

g = randint(1,n)
a1 = randint(1,n)
a2 = randint(1,n)

k1 = pow(g,a1*(p-1),n)
k2 = pow(g,a2*(q-1),n)

b1 = randint(1,n)
b2 = randint(1,n)

c1 = (pow(k1,b1,n)*flag)%n
c2 = (pow(k2,b2,n)*flag)%n

print("n=",n)
print("k1=",k1)
print("k2=",k2)
print("c1=",c1)
print("c2=",c2)

n= 67944616715540041494243707801169601711955678954104061566037501801001319586091022806334351245986706604861253120616958805527215060331484842414608222119998042102906652742837262327108589865853702123438285128216061064163968636436873256782548832337937479385449143497494793808181098183822516797451717146775408402251
k1= 23076418967657048144428921048336695124523055642977012614488429221297541044185740158991808808388844770380578511393718713035911513214464794314385850628654053482319127928761331701897904470579323989202567614315841991422837103284965741014164152265901420603907749042862790429273867698775727296271815976573962338158
k2= 6991632310124089435701240220781055373688305395640885835060229075216670782532097511042800617380391320018414291933317253218012264601879310564869170315686211820657274585605731156032020016356005728320405138935524421497221933430001000304836003301375311909307423272244417440644577851474226950844787216843937103052
c1= 41738526264853349252733490966488283169502571029375503952015425014153105702523021754697561873392135434875242215017237853310490583165780829720218204912574128430314842414672560855972611795426357901583514319877907028968286656554746720043435441356035168649438513791013525974442181394482510162012205019636038224685
c2= 20618977555661583827427904863304009172518108973116435243009145527254045055154728197450704337361232864836393750821416406821915884023488721799509170400820354023019101611886599894087632559336933645351059508044815802015069211201048539037539316735781388776400479944004577792276559637652083115865286131188830196645

import libnum
p=libnum.gcd(k1-1,n)
q=n//p
flag1=c1%p
flag2=c2%q
flag=libnum.solve_crt([flag1,flag2],[p,q])
print(libnum.n2s(flag))